가상 메모리

가상 메모리

물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술이다. 프로세스는 운영체제가 어디에 있는지, 물리 메모리의 크기가 어느 정도인지 신경 쓰지 않고 메모리를 마음대로 사용할 수 있다. 이러한 가상 메모리 시스템은 메모리 관리자가 운영한다.

가상 메모리에서 메모리 관리자가 사용할 수 있는 메모리의 전체 크기는 물리 메모리(실제 메모리)와 스왑 영역을 합한 크기다. 메모리 관리자는 물리 메모리와 스왑 영역을 합쳐 프로세스가 사용하는 가상 주소를 실제 메모리의 물리 주소로 변환하는데 이러한 작업을 동적 주소 변환(DAT)라고 한다.

매핑 테이블

메모리 관리자는 가상 주소와 물리 주소를 일대일로 매핑한 테이블로 관리한다. 위 매핑 테이블은 세그먼테이션 매핑 테이블 예시이다. 프로세스 A의 어떤 값이 필요하다면, 물리 메모리의 세그먼트 0에서 원하는 데이터를 가져오면 된다.

페이징과 세그먼테이션

메모리 관리 방식은 크게 고정 분할 방식인 페이징과 가변 분할 방식인 세그먼테이션으로 나뉜다. 페이징은 페이지 매핑 테이블을 사용해 주소를 변환하고, 세그먼테이션은 세그멘테이션 매핑 테이블을 사용해 주소를 변환한다.

지역성

기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아닌 특정 영역에 집중되는 성질을 나타낸다.

• 공간의 지역성: 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높음
• 시간의 지역성: 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높음
• 순차적 지역성: 작업이 순서대로 진행됨

지역성 이론은 특히 캐시에서 이용되는 이론이다. 캐시는 시간적으로나 지역적으로 가까이 있는 데이터를 가져옴으로써 캐시 적중률을 높인다.

논리 주소, 가상 주소, 물리 주소

가상 메모리 시스템은 프로세스가 물리 메모리를 직접 사용하는 대신 논리 주소(Logical Address)와 가상 주소(Virtual Address)를 사용하여 메모리에 접근하도록 설계되어 있다. 이러한 주소를 물리 주소(Physical Address)로 변환하는 역할은 메모리 관리 유닛(MMU)이 담당한다.

• 논리 주소 (Logical Address): CPU가 생성하는 주소로, 프로그램의 관점에서 사용하는 주소

• 가상 주소 (Virtual Address)

  • 운영체제가 정의한 가상 메모리 공간의 주소로, 논리 주소와 1:1 매핑
  • 논리 주소와 가상 주소는 사실상 동일한 경우가 많음
  • 논리 주소는 사용자 관점, 가상 주소는 운영체제 관점에서 표현된다는 점이 주요 차이

• 물리 주소 (Physical Address)

  • 실제 메모리(RAM)의 주소로, 하드웨어가 메모리에 접근할 때 사용하는 주소
  • 가상 주소는 메모리 관리 유닛(MMU)에 의해 물리 주소로 변환

페이징 기법

고정 분할 방식으로 메모리를 관리하는 기법이다. 가상 주소 공간과 물리 주소 공간을 같은 크기로 나누어 사용한다. 가상 주소 공간에서 분할된 각 영역을 페이지, 물리 주소 공간의 각 영역을 프레임이라 부른다. 가상 주소의 분할된 각 영역을 페이지라고 부르며 물리 메모리의 각 영역은 가상 주소의 페이지와 구분하기 위해 프레임이라고 부른다. 페이지와 프레임의 크기는 같다.

페이지 5의 프레임과 같이 invalid로 표시된 부분은 스왑 영역에 있다는 의미이다.

주소 변환 과정

편의를 위해 가상 주소 공간과 물리 주소 공간을 똑같이 10B로 나눴다.

• 가상 주소 30번의 주소 변환 과정

  1. 페이지를 찾는다. 30번은 페이지 3의 0번 위치에 있다.
  2. 페이지 3의 실제 물리 주소는 프레임 1에 있다.
  3. 최종적으로 프레임 1의 0번 위치에 접근한다. 이 주소가 가상 주소 30번의 물리 주소다.

• 가상 주소 18번의 주소 변환 과정

  1. 페이지를 찾는다. 18번은 페이지 1의 8번 위치에 있다.
  2. 페이지 1의 실제 물리 주소는 프레임 3에 있다.
  3. 최종적으로 프레임 3의 8번 위치에 접근한다. 이 주소가 가상 주소 18번의 물리 주소다.

정형화된 주소 변환

이제 주소 변환 과정을 정형화해 보자. 페이징 기법에서는 가상 주소를 VA(Virtual Address) = <P, D>로 표현한다. P는 page, D는 distance를 의미한다. 위 예시에서 가상 주소 30번을 정형화하면, VA = <3, 0>으로 작성할 수 있다.

물리 주소는 PA(Physical Address) = <F, D>로 표현한다. F는 frame을 의미한다. 위 예시에서 프레임 1의 0번 위치를 정형화하면 PA = <1, 0>으로 작성할 수 있다.

실제 컴퓨터는 2진법을 사용하므로 한 페이지의 크기는 2의 지수승이다. 따라서 주소는 다음과 같이 변환된다.

P = (VA) / (page size)
D = (VA) % (page size)

TLB

가상 주소를 물리 주소로 변환하는 작업은 CPU 내 MMU가 담당한다. 작업은 다음과 같은 과정을 거친다.

1. MMU가 메모리에 있는 페이지 매핑 테이블에 접근해 물리 주소로 변환한다.
2. 변환된 물리 주소를 이용해 필요한 데이터를 가져온다. 위 과정에서 메모리에 접근하기 때문에 CPU 안에 있는 레지스터나 캐시에 접근할 때보다 시간이 오래걸린다. 이는 CPU 성능 저하로 이어진다.

위 문제를 해결하기 위해 페이지 매핑 테이블의 일부를 CPU 안쪽으로 가져오는데 이를 변환 색인 버퍼(TLB: Translation Look-ahead Buffer)라고 한다. TLB는 캐시된 페이지 매핑 테이블로 지역성 이론에 근거해 현재 사용 중이거나 사용이 예상되는 페이지 테이블의 일부를 CPU 안쪽으로 가져온다.

세그먼테이션 기법

세그먼테이션에서는 하나의 연속된 공간을 세그먼트라고 한다.

주소 변환 과정

세그먼테이션 기법에선 가상 주소를 VA = <S, D>로 표현한다. S는 Segment number, D는 distance를 의미한다.

주소 변환 과정은 다음과 같다.

1. 프로세스 A는 세그먼트 0으로 분할되었으므로 S는 0, D는 32다. 따라서 가상 주소 VA = <0,32> 다.
2. 세그먼트 0의 시작주소 120을 알아낸 후 거리 32를 더해 물리 주소 152를 구한다. 이때 메모리 관리자는 거리가 세그먼트의 크기보다 큰지 점검한다. 크다면 메모리를 벗어나는 것이므로 해당 프로세스를 강제 종료한다.
3. 물리 주소 152번에 접근해 원하는 데이터를 읽거나 쓴다.

세그먼테이션 테이블에는 물리 메모리의 시작 주소를 나타내는 주소와 세그먼트의 크기를 나타내는 limit가 있다. 물리 메모리에 접근할 때마다 거리 D의 크기가 limit보다 작은지 매번 확인한다.

페이징 기법과 세그먼테이션 기법 비교

요구 페이징

운영체제는 필요한 모듈만 메모리에 올려 실행하고 나머지 모듈은 필요하다고 판단될 때 메모리로 불러오는데 이를 요구 페이징이라고 한다.

프로세스의 일부만 메모리로 가져오는 이유는 다음과 같다.

• 메모리를 효율적으로 관리: 메모리가 꽉 차면 관리하기 어려우므로 가능하면 적은 양의 프로세스만 유지한다.
• 응답 속도 향상: 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행한다.

가상 메모리 시스템에서 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다. 페이지가 스왑 영역에 있는 경우는 크게 두 가지다.

• 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우
• 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우 어떤 것이든 스왑 영역에 있는 모듈은 물리 메모리로 가져오는 스왑인 과정을 거쳐야 사용 가능하기 때문에 페이지 매핑 테이블에는 페이지가 메모리에 있는지, 스왑 영역에 있는지 표시해야 한다. 이때 사용하는 비트가 유효 비트다.

페이지 매핑 테이블 엔트리 구성

페이지 매핑 테이블의 각 엔트리 구성은 다음과 같다.

• 페이지 번호

• 플래그 비트

  • 접근 비트(access bit): 페이지가 메모리에 올라온 후 사용한 적이 있느지 알려준다.
  • 변경 비트(modified bit): 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 알려준다.
  • 유효 비트(valid bit): 페이지가 실제 메모리에 있는지 나타낸다.
  • 읽기 비트, 쓰기 비트, 실행 비트(read bit, write bit, execute bit): 각 작업에 대한 실행 권한을 나타낸다. 권한이 없는 작업 접근을 차단하는 데 사용된다. 따라서 위 3 비트를 합쳐 접근 권한 비트라고도 한다.
• 주소 필드

페이징 부재

프로세스가 페이지를 요청했을 때 해당 페이지가 메모리에 없는 상황을 페이지 부재라고 한다. 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다.

만약 메모리에 빈 프레임이 있다면, 그곳에 페이지를 올리고 페이지 매핑 테이블을 갱신하면 된다. 하지만 빈 프레임이 없다면 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보낸 후 해당 페이지를 가져와야 한다. 이때 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘을 페이지 교체 알고리즘이라고 하며, 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지(victim page)라고 한다.

페이지 교체 알고리즘

메모리가 꽉 차서 메모리에 있는 페이지를 스왑 영역으로 보내야할 때 보낼 페이지를 결정하는 알고리즘이다.

무작위 페이지 교체 알고리즘

스왑 영역으로 보낼 페이지를 특별한 로직 없이 무작위로 선정한다. 지역성을 전혀 고려하지 않기 때문에 성능이 좋지 않아 거의 사용되지 않는다.

FIFO 페이지 교체 알고리즘

큐를 이용해 시간상 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다.

무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어진다.

최적 페이지 교체 알고리즘

앞으로 사용하지 않을 페이지를 스왑 영역으로 보내는 이상적인 알고리즘이다. 실제로 미래의 접근 패턴을 안다는 것은 불가능하기 때문에 구현이 불가능한 이론적인 알고리즘이다.

LRU(Least Recently Used) 페이지 교체 알고리즘

페이지에 접근한 시간을 기준으로 대상 페이지를 선정한다. 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다.

접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다는 것이 단점이다.

LFU(Least Frequently Used) 페이지 교체 알고리즘

페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다. 일반적인 경우 위 LRU 알고리즘과 성능이 비슷하다고 알려져 있다.

페이지 접근 횟수를 표시하는 데 추가 공간이 필요하므로 낭비되는 메모리 공간이 많다는 것이 단점이다.

NUR(Not Used Recently) 페이지 교체 알고리즘

LRU나 LFU와 성능이 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘이다. 추가 비트 2개만 사용하여 미래를 추정한다.

• 참조 비트: 페이지에 접근하면 1이 된다.
• 변경 비트: 페이지가 변경되면 1이 된다. 모든 페이지의 초기 상태는 (0, 0)이다. 이 상태에서 페이지에 읽기 또는 실행 같은 접근이 발생하면 (1, 0)으로 바뀐다. 만약 쓰기 또는 추가 같은 변경이 일어나면 (0, 1)이 된다. 두 연산이 모두 발생하면 (1, 1)이 된다.

페이지마다 접근 비트와 변경 비트를 두고 (0, 0), (0, 1), (1, 0), (1, 1)의 순서대로 대상 페이지를 선정한다.

흔한 경우는 아니지만 모든 페이지의 비트가 (1, 1)일 때는 NUR 페이지 교체 알고리즘을 정상적으로 적용할 수 없기 때문에 모든 페이지 비트를 (0, 0)으로 초기화한다.

2차 기회 페이지 교체 알고리즘

FIFO 페이지 알고리즘과 마찬가지로 큐를 사용하지만, 특정 페이지에 접근해 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다는 차이점이 있다.

성능은 LRU, LFU, NUR 페이지 교체 알고리즘보다 약간 낮고 FIFO 페이지 교체 알고리즘보다 약간 높은 것으로 알려져있다. 그러나 큐를 유지하는 비용이 높고, 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다는 단점이 있다.

시계 페이지 교체 알고리즘

시계 페이지 교체 알고리즘은 원형 큐를 사용한다.

대상 페이지를 선정하는 포인터와 접근 비트가 있다. 대상 포인터가 가리키는 페이지가 스왑으로 옮겨지고, 해당 포인터는 아래쪽으로 이동한다. 접근 비트가 1이면 0으로 만들고 다시 한 칸 밑으로 이동한다.

NUR 페이지 교체 알고리즘보다 추가 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 것이 단점이다.

스레싱

여러 프로세스를 동시에 실행하게 되어 메모리가 꽉 찬 후에는 새로운 프로그램을 메모리에 올리기 위해 새로운 프로그램을 메모리에 올리기 위해 기존 프로그램을 스왑 영역으로 옮기는 횟수가 잦아진다.

이와 같이 프로세스가 많이 실행되고 하드디스크 입출력이 너무 많아져 작업이 멈춘 것 같은 상태를 스레싱이라 한다.

스레싱은 각 프로세스에 프레임을 할당하는 문제와도 연결된다. 실행 중인 여러 프로세스에 프레임을 얼마나 나누어 주느냐에 따라 시스템의 성능이 달라진다. 너무 적은 프레임을 할당한다면 페이지 부재가 빈번하게 일어날 것이고, 너무 많은 프레임을 할당한다면 메모리를 낭비해 전반적인 시스템 성능이 낮아질 것이다.

프레임 할당 방식

위에서 언급한 문제를 최소화하기 위해 남아 있는 프레임을 실행 중인 프로세스에 적절히 나누어 주는 정책이 필요하다. 프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분된다.

정적 할당

프로세스 실행 초기에 프레임을 나누어 준 후 그 크기를 고정하는 방식이다.

• 균등 할당: 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당

  • 한계

    • 크기가 큰 프로세스의 경우 페이지 부재가 빈번하게 발생
    • 크기가 작은 프로세스의 경우 메모리 낭비가 발생한다.

• 비례 할당: 프로세스의 크기에 비례하여 프레임을 할당

  • 한계

    • 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못함
    • 사용하지 않을 메모리를 처음부터 미리 확보해 공간을 낭비

동적 할당

프로세스를 실행하는 중에 시시각각 변하는 요청에 따라 프레임을 나누어 주기도 하고 회수하기도 하는 방식이다. 작업 집합 모델을 사용하는 방식과 페이지 부재를 사용하는 방식이 있다.

• 작업집합 모델: 지역성 이론을 기반으로 가장 최근 접근한 프레임이 이후에도 참조될 가능성이 높다는 가정에서 출발해 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고, 집합에 있는 페이지들을 물리 메모리에 유지하여 프로세스의 실행을 돕는다.
• 페이지 부재 빈도: 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식으로 상한선과 하한선을 설정한다. 상한선을 초과하면 프레임을 늘리고, 하한선 밑으로 내려가면 프레임을 회수한다.